#include <stdio.h>
#include <stdlib.h>

typedef char dataType;
typedef struct BtreeNode {
    dataType data;
    struct BtreeNode *left;
    struct BtreeNode *right;
} BtreeNode, *Btree;

BtreeNode * newNode(dataType n) {
    BtreeNode * newNode = (BtreeNode *)malloc(sizeof(BtreeNode));
    if (newNode == NULL) {
        return NULL;
    }
    newNode->data = n;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

//求树的高度
int leftHeight(Btree t) {
    if (t == NULL) {
        return 0;
    }
    if (t->left == NULL && t->right == NULL) {
        return 1;
    }
    return leftHeight(t->left) > leftHeight(t->right) ? leftHeight(t->left) + 1 : leftHeight(t->right) + 1;
}

int leftCount(Btree t) {
    if (t == NULL) {
        return 0;
    }
    if (t->left == NULL && t->right == NULL) {
        return 1;
    }
        return leftCount(t->left) + leftCount(t->right);
}
//index是当前处理的字符的下标
BtreeNode *CreateTree(char *str,int *index) {
    char currChar=str[(*index)++];
    if (currChar == '#') {
        return NULL;
    }
    BtreeNode *newNode = (BtreeNode *)malloc(sizeof(BtreeNode));
    newNode->data = currChar;
    newNode->left = CreateTree(str,index);
    newNode->right = CreateTree(str,index);
    return newNode;
}
int main(void) {
    BtreeNode *node1 = newNode('a');
    BtreeNode *node2 = newNode('b');
    BtreeNode *node3 = newNode('c');
    BtreeNode *node4 = newNode('d');
    BtreeNode *node5 = newNode('e');
    BtreeNode *node6 = newNode('f');
    //构建结构
    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node4->right = node5;
    node5->left = node6;
    return 0;
}
